use std::rc::Rc;
use std::cell::RefCell;

fn main() {
    // 不加main函数，会提示要加
}


// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
  pub val: i32,
  pub left: Option<Rc<RefCell<TreeNode>>>,
  pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
  #[inline]
  pub fn new(val: i32) -> Self {
    TreeNode {
      val,
      left: None,
      right: None
    }
  }
}


impl Solution {
    pub fn tree2str(root: Option<Rc<RefCell<TreeNode>>>) -> String {
        if root.is_none() {
            return "".to_string();
        }
        let node = root.unwrap();
        let mut ret = node.as_ref().borrow().val.to_string();
        let mut node_borrow = node.as_ref().borrow_mut();
        let (left, right) = (Solution::tree2str(node_borrow.left.take()), Solution::tree2str(node_borrow.right.take()));

        match (left.len(), right.len()) {
            (0, 0) => ret,
            (0, _) => format!("{}()({})", ret, right),
            (_, 0) => format!("{}({})", ret, left),
            _ => format!("{}({})({})", ret, left, right),
        }
    }
}


impl Solution2 {
    pub fn tree2str(root: Option<Rc<RefCell<TreeNode>>>) -> String {
        fn dfs(root: Option<Rc<RefCell<TreeNode>>>) -> String {
            if let Some(root) = root {
                let root = root.borrow();
                let val = root.val.to_string();
                return match (root.left.clone(), root.right.clone()) {
                    (None, None) => val,
                    (_, None) => format!("{}({})", val, dfs(root.left.clone())),
                    (_, _) => format!("{}({})({})", val, dfs(root.left.clone()), dfs(root.right.clone())),
                };
            }
            "".to_string()
        }
        dfs(root)
    }
}


impl Solution3 {
    pub fn tree2str(t: Option<Rc<RefCell<TreeNode>>>) -> String {
        // Passed 0ms 2.5mb
        fn pre_order(node: Option<Rc<RefCell<TreeNode>>>, res: &mut String) {
            if let Some(node) = node {
                let left = node.borrow_mut().left.take();
                let right = node.borrow_mut().right.take();
                res.push_str(&node.borrow().val.to_string());
                match (left, right) {
                    (Some(left), Some(right)) => {
                        res.push('(');
                        pre_order(Some(left), res);
                        res.push_str(")(");
                        pre_order(Some(right), res);
                        res.push(')');
                    }
                    (Some(left), None) => {
                        res.push('(');
                        pre_order(Some(left), res);
                        res.push(')');
                    }
                    (None, Some(right)) => {
                        res.push_str("()(");
                        pre_order(Some(right), res);
                        res.push(')');
                    }
                    _ => ()
                }
            }
        }
        let mut res = String::new();
        pre_order(t, &mut res);
        res
    }
}
